package datastructure.linkedlist;

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020-03-20
 */
public class Josepfu {

    public static void main(String[] args) {
        CycleSingleLinkedList list = new CycleSingleLinkedList();
        list.addBoys(5);
        list.showBoy();
        System.out.println("```````````````````````````````");
        list.countBoy(1,2,5);
    }

}

/**
 * 单向环形链表
 */
class CycleSingleLinkedList {

    private Boy first = null;

    /**
     * 创建环形链表
     *
     * @param nums 指定节点数
     */
    public void addBoys(int nums) {
        if (nums < 1) {
            System.out.println("nums值不正确~~~~");
            return;
        }
        // 辅助指针
        Boy curBoy = null;
        // 使用for循环来创建环形链表
        for (int i = 1; i <= nums; i++) {
            Boy boy = new Boy(i);
            if (i == 1) {
                // 如果是第一个节点 赋值给first
                first = boy;
                // 构成环形
                first.setNext(first);
                // 现在第一个节点就是当前节点
                curBoy = first;
            } else {
                // 当前节点的下个节点变成添加的新节点
                curBoy.setNext(boy);
                // 新节点的下一个节点指向first
                boy.setNext(first);
                // 新节点变成当前节点
                curBoy = boy;
            }
        }
    }

    /**
     * 打印节点
     */
    public void showBoy() {
        if (first == null) {
            System.out.println("暂无节点数据~~~~");
            return;
        }
        Boy curBoy = first;
        while (curBoy != null) {
            System.out.println(curBoy);
            if (first == curBoy.getNext()) {
                break;
            }
            curBoy = curBoy.getNext();
        }
    }

    /**
     * 约瑟夫问题
     *
     * @param startNo  从第几个节点开始
     * @param countNum 每次数多少次
     * @param nums     最初圈内有多少节点
     */
    public void countBoy(int startNo, int countNum, int nums) {
        // 校验参数
        if (first == null || startNo < 1 || startNo > nums) {
            System.out.println("参数错误~~~~");
            return;
        }
        // 即first后面的节点
        Boy helper = first;
        while (helper.getNext() != first) {
            helper = helper.getNext();
        }
        // 在开始之前 应该先对原先环形队列开始移动
        for (int i = 0; i < startNo - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        while (helper != first) {
            // 让first 和 helper 同时移动countNum - 1下
            for (int j = 0; j < countNum - 1; j++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            System.out.print(first.getId() + "号节点出圈");
            // 出圈 原本first出去
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.println("最后留在圈中的节点：" + first.getId());
    }

}

class Boy {
    private int id;
    private Boy next;

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }

    public Boy(int id) {
        this.id = id;
    }

    @Override
    public String toString() {
        return "Boy{" +
                "id=" + id +
                '}';
    }
}